package day5;

import java.util.Arrays;

//快速排序
public class Demo3 {
    public static void main(String[] args) {
        int nums[]={11,23,45,66,22,7};
        System.out.println("排序前："+ Arrays.toString(nums));
        quickSort(nums,0, nums.length-1);
        System.out.println("排序后："+ Arrays.toString(nums));
    }
    //实现快速排序
    public static void quickSort(int nums[],int begin,int end){
        //出口
        if (begin<end){
            //1.计算基准数下标的方法
            int index=getIndex(nums,begin,end);
            //2.使用递归对前半部分元素再继续排序
            quickSort(nums,begin,index-1);
            //2.使用递归对后半部分元素再继续排序
            quickSort(nums,index+1,end);
        }
    }
    //给基准数找到正确下标
    public static int getIndex(int nums[],int begin,int end) {
        //1.设置基准数，假设第一个元素是基准数
        int temp = nums[begin];
        //从后往前比较 当元素大于基准数  end-1 再继续扫描
        while(begin<end) {
            while (begin<end && nums[end] >= temp) {
                end--;
            }
            //如果元素小于基准数才能出循环   end下标的值赋给begin
            nums[begin] = nums[end];
            //再从前往后比较，如果小于基准数 begin+1 再继续扫描
            while (begin<end && nums[begin] <= temp) {
                begin++;
            }
            //如果大于基准数才会出现循环，begin位置的值赋值给end
            nums[end] = nums[begin];
        }
        //如果出了外层循环，begin和end是相等的，这个位置就一定是基准数的下标
        nums[end]=temp;
        return end;
    }
}
